%% @author Robert Ahrens <mindangels@yahoo.com>
-module(graph_search).

-compile(export_all).

-export([
         backtrack/3,
         backtrack/4,
         depth_first/3,
         depth_first/4,
         % Logging utils
         full_log/5,
         no_log/5
        ]).

-record(node, {sl=[], nsl=[], de=[]}).


%% @spec backtrack(Start::graph_node(), Goal::function(), Children::function(), Log::function())
%% @doc Do backtrack search through the graph starting from Start.  
%% Return the path from Start to the first goal state (the first graph
%% state, GS, for which Goal(GS) returns true).  Return fail if no such
%% state is found.
%%     Goal is a function that maps graph_node() -> bool()
%%     Children is a function that maps graph_node() -> [graph_node()]
%%     Log is a logging function: 
%%         Log(Direction::atom(),
%%             CurrentState::graph_node(),
%%             StateList::[graph_node()],
%%             NewStateList::[graph_node()],
%%             DeadEnds::[graph_node()]
%%         ) -> ok
%% 
backtrack(StartState, Goal, Children, Log) 
  when is_function(Goal) andalso 
       is_function(Children) andalso 
       is_function(Log) ->
    io:format("Testing log function ...~n"),
    Log(odin, dva, tree, chetirye, pyat),
    bt_fwd([StartState], [StartState], [], StartState, Goal, Children, Log).


%% @spec backtrack(StartState::graph_node(), Goal::function(), Children::function()) -> [graph_node()] | fail
%% @doc Same as backtrack/4 but without logging.
backtrack(StartState, Goal, Children) ->
    backtrack(StartState, Goal, Children, fun no_log/5).


bt_fwd(SL, [], DE, CS, _, _, Log) ->
    Log(fail, SL, [], DE, CS),
    fail;
bt_fwd(SL, NSL, DE, CS, Goal, Children, Log) ->
    Log(fwd, SL, NSL, DE, CS),
    case Goal(CS) of
        true ->
            SL;
        false ->
            %% TODO: Better efficiency -- maintain Seen separately?
            case Children(CS) -- (SL ++ NSL ++ DE) of
                [] ->
                    bt_back(SL, NSL, DE, CS, Goal, Children, Log);                    
                NewChildren = [First|_] ->
                    bt_fwd([First|SL], NewChildren ++ NSL, DE, First, Goal, Children, Log)
            end
    end.
                    
                    
bt_back([CS|SL2], NSL, DE, CS, Goal, Children, Log) ->
    Log(back, [CS|SL2], NSL, DE, CS),
    %% HACK: L&S's algorithm (p97) expects that the [] case
    %% below will never happen.  But either they are wrong or
    %% I misunderstand their pseudocode.
    %% NOTE: On further reflection, I seem to recall having the
    %% same issue when I implemented the damn thing in Python
    %% last year.  So maybe their pseudocode just sucks.
    case tl(NSL) of
        [] -> 
            fail;
        NSL2 ->
            bt_back(SL2, NSL2, [CS|DE], hd(NSL2), Goal, Children, Log)
    end;
bt_back(OtherSL, NSL, DE, CS, Goal, Children, Log) ->
    Log(switching, OtherSL, NSL, DE, CS),
    bt_fwd([CS|OtherSL], NSL, DE, CS, Goal, Children, Log).



depth_first(StartState, Goal, Children) ->
    depth_first(StartState, Goal, Children, fun log/4).


depth_first(StartState, Goal, Children, Log)
  when is_function(Goal) andalso
       is_function(Children) andalso
       is_function(Log) ->
    dfs([StartState], [], Goal, Children, Log).


dfs([CS|Open], Closed, Goal, Children, Log) ->
    Log(dfs, CS, [CS|Open], Closed),
    case Goal(CS) of
        true ->
            {ok, CS};
        false ->
            NewClosed = [CS|Closed],
            NewStates = Children(CS) -- (Open ++ NewClosed),
            dfs(NewStates ++ Open, NewClosed, Goal, Children, Log)
    end;
dfs([], _, _, _, _) ->
    fail.


breadth_first(StartState, Goal, Children) ->
    breadth_first(StartState, Goal, Children, fun log/4).


breadth_first(StartState, Goal, Children, Log)
  when is_function(Goal) andalso
       is_function(Children) andalso
       is_function(Log) ->
    bfs([StartState], [], Goal, Children, Log).


bfs([CS|Open], Closed, Goal, Children, Log) ->
    Log(bfs, CS, [CS|Open], Closed),
    case Goal(CS) of
        true ->
            {ok, CS};
        false ->
            NewClosed = [CS|Closed],
            NewStates = Children(CS) -- (Open ++ NewClosed),
            bfs(Open ++ NewStates, NewClosed, Goal, Children, Log)
    end;
bfs([], _, _, _, _) ->
    fail.


%%% TODO: Best-first.  Take a function to usort the states with.
best_first(StartState, Goal, Children, Heuristic) ->
    best_first(StartState, Goal, Children, Heuristic, fun log/4).


best_first(StartState, Goal, Children, Heuristic, Log) 
  when is_function(Goal) andalso
       is_function(Children) andalso
       is_function(Heuristic) andalso
       is_function(Log) ->
    best_fs([StartState], [], Goal, Children, Heuristic, Log).


best_fs([CS|Open], Closed, Goal, Children, Heuristic, Log) ->
    Log(best_fs, CS, [CS|Open], Closed),
    case Goal(CS) of
        true ->
            {ok, CS};
        false ->
            NewClosed = [CS|Closed],
            NewStates = Open ++ Children(CS) ++ NewClosed,
            OrderedNS = lists:usort(Heuristic, NewStates),
            best_fs(OrderedNS, NewClosed, Goal, Children, Log)
    end;
best_fs([], _, _, _, _, _) ->
    fail.


%%% LOGGING UTILS

log(SearchType, CS, Open, Closed) ->
    io:format("~p~nCS: ~p~nOpen: ~p~nClosed: ~p~n~n", [SearchType, CS, Open, Closed]).


no_log(_, _, _, _, _) -> ok.


full_log(Mode, SL, NSL, DE, CS) ->
    io:format("~p~nCS : ~p~nSL : ~p~nNSL : ~p~nDE : ~p~n~n", [Mode, CS, SL, NSL, DE]).
